"""
0-1 knapsack problem
对于DP的问题，首先要明确贝尔曼方程的形式，也就是前一个状态或者后一个状态的确定
"""

weight_n = [1, 2, 4, 5, 6]
value_n = [3, 2, 5, 7, 1]
cap = 7

# 创建DP二维数组
DP = [[0 for _ in range(cap + 1)] for _ in range(len(weight_n) + 1)]

for j in range(1, cap+1):
    for i in range(1, len(weight_n) + 1):
        if weight_n[i-1] > j:
            continue
        else:
            DP[i][j] = max(DP[i-1][j], DP[i-1][j - weight_n[i-1]] + value_n[i-1])


"""
递归-组合问题 
从一个长度为n的数组里面，选k个数
首先要明确递归函数的退出
"""

arr = [1, 2, 3, 4, 5]
k = 5
res = []
path = []


def backtracking(alist, k, path, res):
    if len(path) == k:
        # 由于列表是引用对象，因此要将path里面的值进行拷贝，添加到res中
        res.append(path[::])
        return
    for i in range(len(alist)):
        """
        切片操作相当于浅拷贝，但是如果列表中的元素是可变对象(列表或者字典)的话，拷贝的是这些元素的地址
        可以理解为原列表与新列表地址里面保存的都是地址，不是单个值
        """
        temp_list = alist[i+1::]
        # 剪枝操作, 如果alist数组中元素个数少于需要个数，即可剪枝
        if k - len(path) > len(alist):
            break
        else:
            # 添加元素到ptah中
            path.append(alist[i])
            # 递归
            backtracking(temp_list, k, path, res)
            # 回溯
            path.pop(-1)

    return res


r = backtracking(arr, k, path, res)


"""
爬楼梯问题
"""

L = 8             # 楼梯总数
arr = [2, 3, 5]   # 几种上法
res = []
path = []


def climb(L, arr, res, path):
    if L == 0:
        return res.append(path[:])

    for i in range(len(arr)):

        if arr[i] > L:
            break
        else:
            path.append(arr[i])
            climb(L-arr[i], arr, res, path)
            path.pop()


climb(L, arr, res, path)
print(res)


"""
组合问题，关键要去重
"""

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        # 类比于上楼梯问题
        candidates.sort()  # 共几种上法,要先排序，为了方便去重
        path = []
        res = []
        self.backtracking(candidates, target, path, res)
        return res

    def backtracking(self, arr, L, path, res):
        if len(res) == 150:
            return res
        if L == 0:
            return res.append(path[:])  # 递归退出循环条件
        for i in range(len(arr)):
            if arr[i] > L:  # 如果上法大于剩余楼梯数，停止
                break
            else:
                path.append(arr[i])
                # 递归，传入的是arr[i:],这一步是为了去重
                self.backtracking(arr[i:], L - arr[i], path, res)
                # 回溯
                path.pop()
        return res